Encoders for encoding data in accordance with a Reed-Solomon error correction code ("ECC") to produce ECC symbols are well known. A conventional encoder that produces "j" ECC symbols includes j Galois Field multipliers. The Galois Field multipliers are associated, respectively, with the j roots of the code generator polynomial, g(x). The encoder also includes feedback adders that combine the products associated with a given data symbol with the results of the encoding of the previous data symbol, and j registers that hold the sums produced by the adders. At the end of the encoding, the j registers contain the ECC symbols.
When a data symbol is supplied to the encoder the symbol is combined with the contents of a last register and the result is supplied to the Galois Field multipliers, which simultaneously multiply the results by the roots of g(x). The product produced by a first Galois Field multiplier updates the first register. The products produced by the remaining Galois Field multipliers are combined, respectively, with the contents of the remaining registers and the results are used to update these registers. The last register is thus updated with the sum of (i) the product produced by the last Galois Field multiplier and (ii) the contents of the preceding register. The updated contents of the last register are then combined with the next data symbol and the result is fed back to the Galois Field multipliers, with the remaining feedback adders adding the products produced by the multipliers to the results of the encoding of the previous data symbol and supplying the sums to update the registers, and so forth. As soon as the last data symbol is encoded, the ECC symbols are read from or clocked out of the j registers and concatenated with the data symbols to produce a data codeword that is transmitted or stored, as appropriate. With such an encoder the latency is the time associated with a single feedback adder, since the adders operate in parallel to produce the updated sums for the registers. Accordingly, the latency is essentially non-existent.
As part of a decoding operation a decoding system manipulates the data symbols of a data code word to produce error syndromes that are then used to locate errors in the data. A conventional error syndrome generator includes j sets of associated update adders, Galois Field multipliers and registers, with each set operating simultaneously and essentially separately to produce the associated error syndrome. Each update adder adds the product produced by the associated Galois Field multiplier to the next data symbol, and updates the associated register with the sum. Each Galois Field multiplier then multiplies the contents of the register by a root of an error syndrome generator polynomial that is associated with the ECC and supplies the product to the associated update adder. The update adder adds the product to the next data symbol, and supplies the sum to the associated register, and so forth. After the last data symbol is supplied to the syndrome generator and added to the products produced by the respective Galois Field multipliers to update the registers, the j registers contain the j error syndromes.
The Galois Field multipliers that are included in the encoder and the syndrome generator are relatively complex components. An article by Gerhard Fettweis and Martin Hassner, A Combined Reed-Solomon Encoder And Syndrome Generator With Small Hardware Complexity, published by IEEE in 1992 describes hardware that uses the same Galois Field multipliers for both the encoding and the syndrome generation. The combined hardware thus uses one-half the number of multipliers that are required for separate encoder and syndrome generator hardware. The article is incorporated herein by reference.
The combined hardware described in the article includes j sets of associated registers, Galois Field multipliers, update adders and feedback adders. The j registers hold updated sums produced by the j associated update adders. Each Galois Field multiplier multiplies the contents of the associated register by a root of the generator polynomial and supplies the product to the associated feedback adder. During encoding operations, an associated AND gate passes to the adder the sum produced by the previous feedback adder. The adder then adds the propagating sum to the product and passes the result both to the associated update adder and through a next AND gate to the next feedback adder. The next feedback adder adds the propagating sum to the product produced by the associated multiplier, and the result is supplied to the associated update adder and through the next AND gate to a next feedback adder, and so forth. The feedback adders and associated AND gates thus form a feedback path in which the adders operate as a chain. During syndrome generation operations, the AND gates essentially break the chain of adders by blocking the propagation of a sum from one feedback adder to the next, and the j sets of associated registers, multipliers and adders operate separately to produce the j error syndromes.
With the combined hardware there is a latency in the encoding operations that corresponds to the time it takes the propagating sum to pass through the chain of j feedback adders. If the chain of adders is long, it restricts the speed with which the data is encoded by setting a minimum time for a clock cycle, since the propagating sum must pass through the entire chain in one clock cycle.
The Fettweis-Hassner article discusses the latency problem and describes a two-stage pipelined circuit that essentially cuts the chain of j feedback adders in half. In the first stage of the two-stage circuit the Galois Field multipliers associated with the first j/2 roots of the generator polynomial are positioned between the update adders and the associated registers. An update adder thus adds a data symbol to the results of the encoding of a previous data symbol, and the associated Galois Field multiplier multiplies the sum by a root of the generator polynomial. The product produced by the Galois Field multiplier is supplied to the associated feedback adder, which adds the product to the sum provided by the previous feedback adder. The resulting sum both updates the associated register and propagates through the remaining adders in the stage and into a delay circuit.
During the n.sup.th clock cycle, the i.sup.th update adder in the first stage produces the sum EQU Y.sub.n,i =(r.sub.n-1,i +d.sub.n)
where r.sub.n-1,i is the contents of the associated register, r.sub.n-1,i =p.sub.n-1,i and p.sub.n-1,i is the propagating sum produced by the associated feedback adder in the previous clock cycle. The sum is then multiplied by a root a.sup.i of the generator polynomial and the product EQU Z.sub.n,i =.alpha..sup.i *(r.sub.n-1,i +d.sub.n)
is then supplied to the feedback adder and added into the next propagating sum, P.sub.n,i-1. The result P.sub.n,i both propagates to the next feedback adder and updates the associated register, such that r.sub.n,i =p.sub.n,i. The sum p.sub.n,j/2-1 produced by the last feedback adder in the stage is held in the delay circuit until the next clock cycle.
When a next data symbol is supplied to the hardware, the delay circuit supplies the propagating sum associated with the previous data symbol to the first feedback adder in the second stage. In the second stage the registers are positioned between the update adders and the Galois Field multipliers, such that the multipliers produce products associated with the previous data symbol, and the update adders provide to the registers updated sums associated with the data symbol that is then being supplied to the hardware. Each multiplier in the second stage multiplies the contents of the associated register, by one of the last j/2 roots of the generator polynomial and supplies the product to the associated feedback adder. The first feedback adder in the second stage adds the product produced by the associated Galois Field multiplier to the sum p.sub.n,j/2-1 supplied by the delay circuit. The result p.sub.n,j/2 is then supplied both to the associated update adder and to the next feedback adder in the chain, such that the propagating sum continues to pass through the chain of j/2 feedback adders in the second stage.
During the n+1.sup.st clock cycle, the m.sup.th register in the second stage contains the sum produced by the update adder in the previous clock cycle r.sub.n-1,m =P.sub.n-l,m +d.sub.n. The sum is then multiplied by the m.sup.th root of the generator polynomial to produce the product EQU Z.sub.n,m =.alpha..sup.m *(P.sub.n-1,m +d.sub.n)
which is supplied to the associated feedback adder and added into the propagating delayed sum P.sub.n,m-1. The result P.sub.n,m propagates to the next feedback adder and to the associated update adder. The update adder adds the sum P.sub.n,m to the next data symbol d.sub.n+1 and the result r.sub.n+1,m= P.sub.n,m +d.sub.n+1 is held in the associated register. The last feedback adder in the system thus produces the propagating sum P.sub.n,j during the n+1.sup.st clock cycle, and the two stages operate as a pipeline.
The two-stage pipeline circuit works well for encoding operations that use ECCs that detect or correct relatively few errors, that is, ECCs that produce relatively small numbers of ECC symbols. The associated latency is the time it takes the propagating sum to pass through the j/2 adders in the second stage, or one-half the latency of the single-stage system. The latency is unacceptable, however, for systems that require ECCs that use greater numbers of ECC symbols. As the Fettweis-Hassner article explains, the chain of adders in the feedback path prevents the coupled stages described above from being used for further pipelining, and complicates efforts to use the combined hardware for relatively long ECCs.